package com.lry.basic.algorithm.dp;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/6/25
 */
//          '.' Matches any single character.
//          '*' Matches zero or more of the preceding element.
//          Note
//            s could be empty and contains only lowercase letters a-z.
//            p could be empty and contains only lowercase letters a-z, and characters like . or *.
//
//            Example 1:
//
//            Input:
//            s = "aa"
//            p = "a"
//            Output: false
//            Explanation: "a" does not match the entire string "aa".
//
//            Example 2:
//
//            Input:
//            s = "aa"
//            p = "a*"
//            Output: true
//            Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
//
//            Example 3:
//
//            Input:
//            s = "ab"
//            p = ".*"
//            Output: true
//            Explanation: ".*" means "zero or more (*) of any character (.)".
//
//            Example 4:
//
//            Input:
//            s = "aab"
//            p = "c*a*b"
//            Output: true
//            Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

public class RegularExpressionMatching {
    public static void main(String[] args) {
        String s = "mississippi";
        String p = "mis*is*p*.";
        System.out.println(isMatch(s, p));
    }
    public static boolean isMatch(String s,String p){
        //deal with null pointer execption
        if(null==s||p==null)return false;
        if(p.startsWith("*")) return false;
        int sLen = s.length(),pLen = p.length();
        boolean[][] dp = new boolean[sLen+1][pLen+1];
        dp[0][0] = true;
        for(int i=1;i<p.length();i++){
            if(p.charAt(i)=='*'&&dp[0][i-1]){
                dp[0][i+1] = true;
            }
        }

        for(int i=0;i<sLen;i++){
            for(int j=0;j<pLen;j++){
                if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='.'){
                    dp[i+1][j+1] = dp[i][j];
                }
                if(p.charAt(j)=='*'){
                    if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
                        dp[i+1][j+1] = dp[i+1][j-1];
                    } else {
                        dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
                    }
                }
            }
        }
        for(int i=0;i<=sLen;i++){
            for(int j=0;j<=pLen;j++){
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        return dp[sLen][pLen];
    }
}
